import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;


public class foilAlgo {

	public static String[] persons;
	public static ArrayList<Literal> pos; // [0] => Literal, First, Second
	public static ArrayList<Literal> neg; // [0] => Literal, First, Second
	public static ArrayList<String> literalsToLearn;
	public static ArrayList<Literal> allLiterals;
	public static HashMap<String, ArrayList<Literal>> allLiteralsWithKnowledgeBase;
	
	public static ArrayList<Literal> tmp_NegLiterals;
	public static ArrayList<Literal> tmp_PosLiterals;
	
	public static File foilData = new File(System.getProperty("user.dir") + "/data/Session4/kinship2.foil");
	
	public static ArrayList<Rule> learnedRules;
	
	
	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		readInput();
    	startFOIL();
    	//printSomething();
	}

	private static void readInput() throws IOException {
        pos = new ArrayList<Literal>();
        neg = new ArrayList<Literal>();
        literalsToLearn = new ArrayList<String>();
        allLiterals = new ArrayList<Literal>();
        allLiteralsWithKnowledgeBase = new HashMap<String, ArrayList<Literal>>();
        
        BufferedReader input = new BufferedReader(
        		new InputStreamReader(
        				new FileInputStream(foilData)));

        String line = "";
        line = input.readLine();
    	// person:
    	line = input.readLine().trim();
    	line = line.substring(0, line.indexOf("."));
    	String[] personSplit = line.split("[,]");
    	persons = new String[personSplit.length];
    	persons = personSplit;

    	line = input.readLine(); // leer

    	// READ rules
    	while( (line = input.readLine()) != null ) {
    		// rule
    		boolean positive = false;
    		line = line.trim();
    		String literalName = line.substring(1, line.indexOf("("));
    		if(line.startsWith("*")) 
    		{
    			positive = false;
    			String[] argvSplit = line.substring(line.indexOf("(")+1, line.indexOf(")")).split("[,]");
    			Atom[] argv = new Atom[argvSplit.length];
    			
    			for (int i = 0; i < argv.length; i++) 
    			{
    				argv[i] = new Atom(argvSplit[i]);
				}
    			
    			Literal lit = new Literal(literalName, argv);
    			allLiterals.add(lit);
    			allLiteralsWithKnowledgeBase.put(lit.getName(), new ArrayList<Literal>());
    			
    		} 
    		else 
    		{
    			positive = true;
    			literalName = line.substring(0, line.indexOf("(") );
    			literalsToLearn.add(literalName);
    			allLiteralsWithKnowledgeBase.put(literalName, new ArrayList<Literal>());
    		}
			while ( !".".equals((line = input.readLine().trim())) ) 
			{
				String[] argSplit = line.split("[,]");
			
				Atom[] argv = new Atom[argSplit.length];
				for (int i = 0; i < argSplit.length; i++) {
					argv[i] = new Atom(argSplit[i]);
				}
				Literal literal = new Literal(literalName, argv);
				
				if (positive)
				{
					pos.add(literal); // ADD POSITIVE EXAMPLE
				}
				
				allLiteralsWithKnowledgeBase.get(literal.getName()).add(literal);
			}
    	} // END read input
    	
    	for(String literalName: literalsToLearn) 
    	{
        	ArrayList<Literal> tmpNeg = new ArrayList<Literal>();
        	for (int i = 0; i < persons.length; i++) 
        	{
    			for (int j = 0; j < persons.length; j++) 
    			{
					Atom[] argv = new Atom[2];
					argv[0] = new Atom(persons[i]);
					argv[1] = new Atom(persons[j]);
					Literal literal = new Literal(literalName, argv);
   					if(!pos.contains(literal))
    					tmpNeg.add(literal);
				}
    		}
        	neg.addAll(tmpNeg);
    	} // END NEG EXAMPLES
        input.close();
        System.out.println("readInput done.");
	}

	
    private static void printSomething() {
    	// AUSGABE
    	System.out.println("Literals to lean:");
    	for(String s: literalsToLearn)
    		System.out.println(s);
    	System.out.println("allLiterals:");
    	for(Literal s: allLiterals)
    		System.out.println(s);
    	System.out.println();
    	System.out.println("positive examples (" + pos.size() + ")");
    	for(Literal s: pos) {
    		System.out.println(s);
    	}
    	System.out.println();
    	System.out.println("negative examples (" + neg.size() + ")");
    	for(Literal s: neg) {
    		System.out.println(s);
    	}  
	}

	private static void startFOIL() 
	{
		ArrayList<Literal> max_NegLiterals = null;
		ArrayList<Literal> max_PosLiterals = null;
		
		learnedRules = new ArrayList<Rule>();
		ArrayList<Literal> MyPos = new ArrayList<Literal>(pos);
		while(!MyPos.isEmpty()) 
		{
			Rule newRule = generateMostGeneralRule(MyPos.get(0)); //most general rule
			ArrayList<Literal> NewRuleNeg = new ArrayList<Literal>(neg);
			
			ArrayList<Literal> allPositiveBindingsForCurrentRule = new ArrayList<Literal>(MyPos);
			
			while(!NewRuleNeg.isEmpty()) 
			{
				Rule tmp_newRule = null;
				double maxFoilGain = -10000;
				
				List<Rule> allNewRules = generateAllRules(newRule);
				for(Rule rule: allNewRules) 
				{
					double foilGain = getFOILGain2(rule, allPositiveBindingsForCurrentRule, NewRuleNeg);
					
					// Relax foil-gain and update newRule
					if (foilGain > maxFoilGain)
					{
						maxFoilGain = foilGain;
						tmp_newRule = rule;
						
						max_NegLiterals = new ArrayList<Literal>(tmp_NegLiterals);
						max_PosLiterals = new ArrayList<Literal>(tmp_PosLiterals);
					}
				}
				
 				newRule = new Rule(tmp_newRule);
				
				// Create subset of NewRuleNeg satisfying tmp_newRule
//				for (Literal lit : max_NegLiterals) 
//				{
//					if (!NewRuleNeg.contains(lit))
//					{
//						NewRuleNeg.remove(NewRuleNeg.indexOf(lit));
//					}
//				}
 				NewRuleNeg.clear();
 				NewRuleNeg.addAll(max_NegLiterals);
 				
				ArrayList<Literal> tempMerge = new ArrayList<Literal>();
				for (Literal lit : pos) 
				{
					if (allPositiveBindingsForCurrentRule.contains(lit) && max_PosLiterals.contains(lit))
					{
						tempMerge.add(lit);
					}
				}
				allPositiveBindingsForCurrentRule.clear();
				allPositiveBindingsForCurrentRule.addAll(tempMerge);
			}
			learnedRules.add(newRule);
			
			// TODO Wrong max pos
			// Create subset of pos satisfying newRule
			for (Literal lit : allPositiveBindingsForCurrentRule) 
			{
				if (MyPos.contains(lit))
				{
					MyPos.remove(lit);
				}
			}
		}
		
		for (Rule rl : learnedRules) 
		{
			System.out.println(rl);
		}
	}

	private static List<Rule> generateAllRules(Rule rule) 
	{
		List<Rule> myList = new ArrayList<Rule>();
		List<Atom[]> varPossibilities = new ArrayList<Atom[]>();
		varPossibilities.add(new Atom[] {new Atom("A"), new Atom("A")});
		varPossibilities.add(new Atom[] {new Atom("B"), new Atom("B")});
		varPossibilities.add(new Atom[] {new Atom("A"), new Atom("B")});
		varPossibilities.add(new Atom[] {new Atom("B"), new Atom("A")});
		varPossibilities.add(new Atom[] {new Atom("A"), new Atom("C")});
		varPossibilities.add(new Atom[] {new Atom("C"), new Atom("B")});
		varPossibilities.add(new Atom[] {new Atom("C"), new Atom("A")});
		varPossibilities.add(new Atom[] {new Atom("B"), new Atom("C")});
		varPossibilities.add(new Atom[] {new Atom("C"), new Atom("C")});
		varPossibilities.add(new Atom[] {new Atom("C"), new Atom("D")});
		
		for(Literal literal: allLiterals) 
		{	
			for(Atom[] argv : varPossibilities) 
			{
				Rule tmpRule = new Rule(rule);
				Literal rightlit = new Literal(literal.getName(), argv);
				
				// Never add the same literal to rule
				//if (rule.getRightLiteral().contains(lit))
				//{
				//	continue;
				//}
				
				
				tmpRule.addRightLiteral(rightlit);
				myList.add(tmpRule);
			}
		}
		
		return myList;
	}

	
	private static Rule generateMostGeneralRule(Literal lit) {
		Atom[] argv = new Atom[lit.getArgv().length];
		VarNames[] varNames = VarNames.values();
		if(argv.length > varNames.length)
			return null;
		for (int i = 0; i < argv.length; i++) {
			argv[i] = new Atom(varNames[i].toString());
		}
		Literal left = new Literal(lit.getName(), argv);
		Rule rule = new Rule();
		rule.addLeftLiteral(left);
		return rule;
	}

	public static double getFOILGain(Rule rule, ArrayList<Literal> posParameter, ArrayList<Literal> negParameter)
	{	
		// Clearing
		tmp_NegLiterals = null;
		tmp_PosLiterals = null;
		
		// Search all distinct vars in left literals
		ArrayList<Atom> allDistinctLeftAtoms = new ArrayList<Atom>();
		for (Literal lit : rule.getLeftLiteral()) 
		{
			for (Atom atom : lit.getArgv()) 
			{
				if (!allDistinctLeftAtoms.contains(atom))
					allDistinctLeftAtoms.add(new Atom(atom.getVarname()));
			}
		}
		
		// Search all distinct vars in right literal
		for (Literal lit : rule.getRightLiteral()) 
		{
			for (Atom atom : lit.getArgv()) 
			{
				if (!allDistinctLeftAtoms.contains(atom))
					allDistinctLeftAtoms.add(new Atom(atom.getVarname()));
			}
		}
		
		// Generate all Combinations
		ArrayList<String[]> allCombinations = new ArrayList<String[]>();
		for (String atom : persons) 
		{
			ArrayList<String[]> initialList = new ArrayList<String[]>();
			String[] initialValue = new String[1];
			initialValue[0] = atom;
			initialList.add(initialValue);
			
			allCombinations.addAll(calcSubstitutions(allDistinctLeftAtoms.size() - 1, initialList));
		}
		
		// Here we store all bindings that exits after adding this new literal
		ArrayList<Literal> temp_pos = new ArrayList<Literal>();
		ArrayList<Literal> temp_neg = new ArrayList<Literal>();	
		
		for (int i = 0; i < allCombinations.size(); i++) 
		{
			Rule concreteRule = fillRuleWithConcreteValues(new Rule(rule), allCombinations.get(i));
			
			boolean neg_binding = false;
			boolean pos_binding = false;
			for (Literal literal : concreteRule.getLeftLiteral())
			{
				if (pos.contains(literal))
				{
					pos_binding = true;
				}
				else if (negParameter.contains(literal))
				{
					neg_binding = true;
				}
			}
			
			// In case that no left literal have a positive binding => go to next combination
			if (!pos_binding && !neg_binding)
			{
				continue;
			}
			
			// Get only the new literal and calculate bindings for it
			Literal lastRightLiteral = concreteRule.getRightLiteral().peek();
			boolean concreteLastRightLiteralExists = false;
			for (Literal literal : allLiteralsWithKnowledgeBase.get(lastRightLiteral.getName())) 
			{
				if (literal.equals(lastRightLiteral))
				{
					concreteLastRightLiteralExists = true;
					break;
				}
			}
			
			for (Literal literal : concreteRule.getLeftLiteral()) 
			{
				// In this case the new rule bind a positive binding
				// The concrete literal have a positive binding => add it to temp_pos
				if (concreteLastRightLiteralExists && pos_binding && !temp_pos.contains(literal))
				{
					temp_pos.add(literal);
				}
				else if (neg_binding && !temp_neg.contains(literal))
				{
					// The concrete literal have a negative binding => add it to temp_neg
					temp_neg.add(literal);
				}
			}
		}
		
		
		// Store negative bindings for later calculation
		tmp_NegLiterals = new ArrayList<Literal>(temp_neg);
		tmp_PosLiterals = new ArrayList<Literal>(temp_pos);
		
		// Now we have all information to calculate foil gain
		double p0 = posParameter.size();
		double n0 = negParameter.size();
		double p1 = temp_pos.size();
		double n1 = temp_neg.size();
		double t = 0;
		
		for (Literal literal : posParameter) 
		{
			if (temp_pos.contains(literal))
				t++;
		}
		
		// If nenner 0, then return negative infinity
		if (p1 + n1 == 0 || p0 + n0 == 0)
			return -1000000;
		
		double firstQu  = p1 / (p1 + n1);
		double secondQu = p0 / (p0 + n0);
		
		// Return foil-gain value
		return t * (log(firstQu, 2) - log(secondQu, 2));
	}
	
	private static double getFOILGain2(Rule rule, ArrayList<Literal> posParameter, ArrayList<Literal> negParameter)
	{
		ArrayList<Literal> temp_pos = new ArrayList<Literal>();
		ArrayList<Literal> temp_neg = new ArrayList<Literal>();
		
		ArrayList<Literal> allLiterals = new ArrayList<Literal>();
		allLiterals.addAll(posParameter);
		allLiterals.addAll(negParameter);

		for (Literal literal : allLiterals) 
		{
			/**
			 * 
			 * 
			 * Substitute left vars with literal atoms
			 * 
			 * 
			 */
			Rule temp_ConcreteRule = new Rule(rule);
			HashMap<String, String> subBound = new HashMap<String, String>();
			ArrayList<String> subUnbound = new ArrayList<String>();
			
			for (int i = 0; i < literal.getArgv().length; i++) 
			{	
				// Current var in rule left is unbounded
				if (!subBound.containsKey(temp_ConcreteRule.getLeftLiteral().get(0).getArgv()[i]))
				{
					subBound.put(temp_ConcreteRule.getLeftLiteral().get(0).getArgv()[i].getVarname()
							, literal.getArgv()[i].getVarname());
					temp_ConcreteRule.getLeftLiteral().get(0).getArgv()[i] = literal.getArgv()[i];
				}
				else
				{
					temp_ConcreteRule.getLeftLiteral().get(0).getArgv()[i] 
							= new Atom(subBound.get(temp_ConcreteRule.getLeftLiteral().get(0).getArgv()[i]));
				}
			}
			
			for (int i = 0; i < literal.getArgv().length; i++) 
			{	
				for (int j = 0; j < temp_ConcreteRule.getRightLiteral().size(); j++) 
				{
					// Unbounded vars on right side are ignored
					if (subBound.containsKey(temp_ConcreteRule.getRightLiteral().get(j).getArgv()[i].getVarname()))
					{
						temp_ConcreteRule.getRightLiteral().get(j).getArgv()[i] 
								= new Atom(subBound.get(temp_ConcreteRule.getRightLiteral().get(j).getArgv()[i].getVarname()));
					}
					else if (!subUnbound.contains(temp_ConcreteRule.getRightLiteral().get(j).getArgv()[i].getVarname()))
					{
						subUnbound.add(temp_ConcreteRule.getRightLiteral().get(j).getArgv()[i].getVarname());
					}
				}
			}
			
			/**
			 * 
			 * 
			 * In temp_ConcreteRule exists no unbounded vars
			 * 
			 * 
			 */

			if (subUnbound.isEmpty())
			{	
				
				
				Literal lastRightLiteral = temp_ConcreteRule.getRightLiteral().peek();
				// Get only the new literal and calculate bindings for it
				
				
				for (Literal literal1 : allLiteralsWithKnowledgeBase.get(lastRightLiteral.getName())) 
				{
					if (literal1.equals(lastRightLiteral))
					{
						if (posParameter.contains(literal))
						{
							temp_pos.add(literal);
							break;
						}
						else if (negParameter.contains(literal))
						{
							temp_neg.add(literal);
							break;
						}
					}
				}
			}
			
			/**
			 * 
			 * 
			 * In temp_ConcreteRule exists unbounded vars
			 * 
			 * 
			 */
			
			
			else
			{
				// Generate all Combinations
				ArrayList<String[]> allCombinations = new ArrayList<String[]>();
				for (String atom : persons) 
				{
					ArrayList<String[]> initialList = new ArrayList<String[]>();
					String[] initialValue = new String[1];
					initialValue[0] = atom;
					initialList.add(initialValue);
					
					allCombinations.addAll(calcSubstitutions(subUnbound.size() - 1, initialList));
				}
				
				for (int i = 0; i < allCombinations.size(); i++) 
				{
					Rule concreteRule = fillRuleWithConcreteValues(new Rule(temp_ConcreteRule), allCombinations.get(i));
					
					// Get only the new literal and calculate bindings for it
					//Literal lastRightLiteral = concreteRule.getRightLiteral().peek();
					boolean allConcreteLiteralExistsInKB = false;
					for (Literal literalRight : concreteRule.getRightLiteral()) 
					{
						allConcreteLiteralExistsInKB = false;
						for (Literal literal1 : allLiteralsWithKnowledgeBase.get(literalRight.getName())) 
						{
							if (literal1.equals(literalRight))
							{
								allConcreteLiteralExistsInKB = true;
								break;
							}
						}
						
						if (!allConcreteLiteralExistsInKB)
							break;
					}
						
					if (allConcreteLiteralExistsInKB && posParameter.contains(literal))
					{
						temp_pos.add(literal);
						break;
					}
					else if (allConcreteLiteralExistsInKB && negParameter.contains(literal))
					{
						temp_neg.add(literal);
						break;
					}
				}
			}	
		}
		
		// Store negative bindings for later calculation
		tmp_NegLiterals = new ArrayList<Literal>(temp_neg);
		tmp_PosLiterals = new ArrayList<Literal>(temp_pos);
		
		// Now we have all information to calculate foil gain
		double p0 = posParameter.size();
		double n0 = negParameter.size();
		double p1 = temp_pos.size();
		double n1 = temp_neg.size();
		double t = 0;
		
		for (Literal literal : posParameter) 
		{
			if (temp_pos.contains(literal))
				t++;
		}
		
		// If nenner 0, then return negative infinity
		if (p1 + n1 == 0 || p0 + n0 == 0)
			return -1000000;
		
		double firstQu  = p1 / (p1 + n1);
		double secondQu = p0 / (p0 + n0);
		
		// Return foil-gain value
		return t * (log(firstQu, 2) - log(secondQu, 2));
	}
	
	
	
	private static double log(double x, int base)
	{
	    return (Math.log(x) / Math.log(base));
	}

	
	private static Rule fillRuleWithConcreteValues(Rule rule,
			String[] currentCombination) 
	{
		
		Rule concretRule = new Rule(rule);
		concretRule.getRightLiteral().clear();
		
		HashMap<String, String> substitutions = new HashMap<String, String>();
		// Check if current combination in left literals exists
//		for (Literal lit : rule.getLeftLiteral()) 
//		{
//			Literal concretLiteral = new Literal(lit.getName(), new Atom[lit.getArgv().length]);
//			for (int j = 0; j < lit.getArgv().length; j++) 
//			{
//				// The current atom has been already used before. 
//				if (substitutions.containsKey(lit.getArgv()[j].toString()))
//				{
//					concretLiteral.getArgv()[j] = new Atom(substitutions.get(lit.getArgv()[j].toString()));
//				}
//				else // The current atom is new. We substitute it with a combination
//				{
//					String currentSubstitution = currentCombination[substitutions.size()];
//					
//					concretLiteral.getArgv()[j] = new Atom(currentSubstitution);
//					substitutions.put(lit.getArgv()[j].toString(), currentSubstitution);
//				}
//			}
//			concretRule.addLeftLiteral(concretLiteral);
//		}
		
		for (Literal lit : rule.getRightLiteral()) 
		{
			Literal concretLiteral = new Literal(lit.getName(), lit.getArgv());
			for (int j = 0; j < lit.getArgv().length; j++) 
			{
				// In case that for the current variable no substitution exits => var isn't init 
				// This vars are unbound
				if (!substitutions.containsKey(lit.getArgv()[j].toString()) 
						&& lit.getArgv()[j].toString().matches("[A-D]"))
				{
					String currentSubstitution = currentCombination[substitutions.size()];
					
					concretLiteral.getArgv()[j] = new Atom(currentSubstitution);
					substitutions.put(lit.getArgv()[j].toString(), currentSubstitution);
				}
				else if (lit.getArgv()[j].toString().matches("[A-D]"))
				// The current atom is new. We substitute it with a combination
				{
					String currentSubstitution = substitutions.get(lit.getArgv()[j].toString());
					
					concretLiteral.getArgv()[j] = new Atom(currentSubstitution);
					//substitutions.put(lit.getArgv()[j].toString(), currentSubstitution);
				}
			}
			concretRule.addRightLiteral(concretLiteral);
		}
		
		return concretRule;
	}
	
	
	
	private static ArrayList<String[]> calcSubstitutions(int depth, ArrayList<String[]> currentCombi)
	{
		if (depth == 0)
			return currentCombi;
		
		ArrayList<String[]> newCombinations = new ArrayList<String[]>();
		
		for (int i = 0; i < currentCombi.size(); i++) 
		{
			for (int j = 0; j < persons.length; j++) 
			{
				// Check if person is already in current combination
				boolean isAlreadyInCombination = false;
				for (int j2 = 0; j2 < currentCombi.get(i).length; j2++) 
				{
					if (persons[j].equals(currentCombi.get(i)[j2]))
					{
						isAlreadyInCombination = true;
						break;
					}
				}
				
				if (isAlreadyInCombination) 
				{
					continue;
				}
				
				// Create new String Array for new Combination with one more Atom
				String[] tempCombi = new String[currentCombi.get(i).length + 1];
				for (int k = 0; k < currentCombi.get(i).length; k++) {
					tempCombi[k] = currentCombi.get(i)[k];
				}
				tempCombi[currentCombi.get(i).length] = persons[j];
				
				newCombinations.add(tempCombi);
			}
		}
		
		return calcSubstitutions(depth -1, newCombinations);
	}
}
